package com.fulin.leetcode;

/**
 * @Description 最长回文数
 * @Author fulin16
 * @Date 2020/10/15 16:00
 **/
public class Num5 {
    public static void main(String[] args) {
        String s = "abcbabc";
        Num5 n = new Num5();
//        System.out.println(n.dpMethod(s));
        System.out.println(n.maxMidExtend(s));
    }


    public String dpMethod(String str){
        int len = str.length();
        int maxLen = 0;
        int low = 0;
        int high = 0;
        //表示从i到j的子字符串是否是回文数
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i++){
            for(int j = 0; j <= i; j++){
                if(j == i){
                    dp[j][i] = true;
                }else if(i - j == 1){
                    dp[j][i] = str.charAt(i) == str.charAt(j);
                }else{
                    dp[j][i] = dp[j + 1][i - 1] && str.charAt(i) == str.charAt(j);
                }
                if(dp[j][i]){
                    if(i - j  >= maxLen ){
                        maxLen = i - j;
                        low = j;
                        high = i;
                    }
                }
            }
        }
        System.out.println(low);
        System.out.println(high);
        return str.substring(low,high+1);
    }

    //中心扩展法
    public String maxMidExtend(String str){
        //对str进行
        if(str == null){
            return null;
        }
        if(str.length() == 1){
            return str;
        }
        int len = str.length();
        int lens = 0;
        int left = 0;
        int right = 0;
        for(int i = 0 ; i < len; i ++){
            int len1 = spendCenter(str,i,i);
            int len2 = spendCenter(str,i,i + 1);

            int temp = Math.max(len1,len2);
            if(temp > lens){
                lens = temp;
                left = i - (temp - 1) / 2;
                right = i + temp/2;
            }
        }

        return str.substring(left,right +1);
    }

    private int spendCenter(String str, int left, int right) {
        while(left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)){
            -- left;
            ++ right;
        }
        return right - left -1;
    }
}
